/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 5/28/2008
 */

#ifndef BTNODE_H
#define BTNODE_H

#include "RecordFile.h"
#include "PageFile.h"
#include <cstring>
#include <vector>
#include <string>

static const int RC_NODE_NOT_EMPTY = -1337;

// Important:
// - This value should always be negative.
// - It is recommended that you leave this value as -1. That way, a buffer can
//   simply be initialized with 0xFF.
static const int EMPTY_VALUE = -1;

class BTNodeByteBuffer {
  public:
    BTNodeByteBuffer() {
      memset(buffer, 0xFF, sizeof(buffer));
      bufferPointer = 0;
    }
    BTNodeByteBuffer(char *existingBuffer) {
      memcpy(buffer, existingBuffer, sizeof(buffer));
      bufferPointer = 0;
    }
    bool appendInt(int integer) {
      if (bufferPointer + sizeof(integer) > sizeof(buffer))
        return false;
      memcpy(buffer + bufferPointer, &integer, sizeof(integer));
      bufferPointer += sizeof(integer);
      return true;
    }
    bool readInt(int& integer) {
      if (bufferPointer + sizeof(integer) > sizeof(buffer))
        return false;
      memcpy(&integer, buffer + bufferPointer, sizeof(integer));
      bufferPointer += sizeof(integer);
      return true;
    }
    const char *rawBuffer() const {
      return buffer;
    }
  private:
    char buffer[PageFile::PAGE_SIZE];
    int bufferPointer;
};

class BTLeafNodeEntry {
  public:
    BTLeafNodeEntry(int k, const RecordId& r) {
      m_key = k;
      m_rid = r;
    }
    int key() const {
      return m_key;
    }
    RecordId rid() const {
      return m_rid;
    }
    bool operator<(const BTLeafNodeEntry& right) const {
      return (m_key < right.key());
    }
  private:
    int m_key;
    RecordId m_rid;
};

typedef std::vector<BTLeafNodeEntry> BTLeafNodeEntries;

/**
 * BTLeafNode: The class representing a B+tree leaf node.
 */
class BTLeafNode {
  public:
    BTLeafNode();

   /**
    * Insert the (key, rid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param rid[IN] the RecordId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, const RecordId& rid);

   /**
    * Insert the (key, rid) pair to the node
    * and split the node half and half with sibling.
    * The first key of the sibling node is returned in siblingKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert.
    * @param rid[IN] the RecordId to insert.
    * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
    * @param siblingKey[OUT] the first key in the sibling node after split.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, const RecordId& rid, BTLeafNode& sibling, int& siblingKey);

   /**
    * Find the index entry whose key value is larger than or equal to searchKey
    * and output the eid (entry id) whose key value &gt;= searchKey.
    * Remember that keys inside a B+tree node are sorted.
    * @param searchKey[IN] the key to search for.
    * @param eid[OUT] the entry number that contains a key larger
    *                 than or equalty to searchKey.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC locate(int searchKey, int& eid) const;

   /**
    * Read the (key, rid) pair from the eid entry.
    * @param eid[IN] the entry number to read the (key, rid) pair from
    * @param key[OUT] the key from the slot
    * @param rid[OUT] the RecordId from the slot
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC readEntry(int eid, int& key, RecordId& rid) const;

   /**
    * Return the pid of the next slibling node.
    * @return the PageId of the next sibling node
    */
    PageId getNextNodePtr() const;

   /**
    * Set the next slibling node PageId.
    * @param pid[IN] the PageId of the next sibling node
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC setNextNodePtr(PageId pid);

   /**
    * Return the number of keys stored in the node.
    * @return the number of keys in the node
    */
    int getKeyCount() const;

   /**
    * Read the content of the node from the page pid in the PageFile pf.
    * @param pid[IN] the PageId to read
    * @param pf[IN] PageFile to read from
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC read(PageId pid, const PageFile& pf);

   /**
    * Write the content of the node to the page pid in the PageFile pf.
    * @param pid[IN] the PageId to write to
    * @param pf[IN] PageFile to write to
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC write(PageId pid, PageFile& pf);

    /*
     * Print the contents of the node (for debugging purposes).
     * @param name[IN] give this node an informative name to be printed
     */
    void print(const std::string& name) const;

  private:
    BTLeafNodeEntries entries;
    static const int MAX_ENTRIES = (PageFile::PAGE_SIZE - sizeof(int)) / (3 * sizeof(int));
    //static const int MAX_ENTRIES = 2;
    PageId nextNode;

    /*
     * Insert a (key, rid) pair to the node (does not check if the node is full).
     * This is for internal use only.
     * @param key[IN] the key to insert
     * @param rid[IN] the RecordId to insert
     */
    void unchecked_insert(int key, const RecordId& rid);
};

class BTNonLeafNodeEntry {
  public:
    BTNonLeafNodeEntry(int k, PageId p) {
      m_key = k;
      m_pid = p;
    }
    int key() const {
      return m_key;
    }
    PageId pid() const {
      return m_pid;
    }
    bool operator<(const BTNonLeafNodeEntry& right) const {
      return (m_key < right.key());
    }
  private:
    int m_key;
    PageId m_pid; // Pointer to nodes with keys >= m_key.
};

typedef std::vector<BTNonLeafNodeEntry> BTNonLeafNodeEntries;

/**
 * BTNonLeafNode: The class representing a B+tree nonleaf node.
 */
class BTNonLeafNode {
  public:
    BTNonLeafNode();

    /**
    * Insert a (key, pid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, PageId pid);

   /**
    * Insert the (key, pid) pair to the node
    * and split the node half and half with sibling.
    * The sibling node MUST be empty when this function is called.
    * The middle key after the split is returned in midKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
    * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
    * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey);

   /**
    * Given the searchKey, find the child-node pointer to follow and
    * output it in pid.
    * Remember that the keys inside a B+tree node are sorted.
    * @param searchKey[IN] the searchKey that is being looked up.
    * @param pid[OUT] the pointer to the child node to follow.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC locateChildPtr(int searchKey, PageId& pid) const;

   /**
    * Initialize the root node with (pid1, key, pid2).
    * @param pid1[IN] the first PageId to insert
    * @param key[IN] the key that should be inserted between the two PageIds
    * @param pid2[IN] the PageId to insert behind the key
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC initializeRoot(PageId pid1, int key, PageId pid2);

   /**
    * Return the number of keys stored in the node.
    * @return the number of keys in the node
    */
    int getKeyCount() const;

   /**
    * Read the content of the node from the page pid in the PageFile pf.
    * @param pid[IN] the PageId to read
    * @param pf[IN] PageFile to read from
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC read(PageId pid, const PageFile& pf);
    
   /**
    * Write the content of the node to the page pid in the PageFile pf.
    * @param pid[IN] the PageId to write to
    * @param pf[IN] PageFile to write to
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC write(PageId pid, PageFile& pf);

    /*
     * Print the contents of the node (for debugging purposes).
     * @param name[IN] give this node an informative name to be printed
     */
    void print(const std::string& name) const;

  private:
    BTNonLeafNodeEntries entries;
    static const int MAX_ENTRIES = (PageFile::PAGE_SIZE - sizeof(int)) / (2 * sizeof(int));
    //static const int MAX_ENTRIES = 2;
    PageId pidFirst; // Pointer to nodes with keys < the first key in this node.

    /*
     * Insert a (key, pid) pair to the node (does not check if the node is full).
     * This is for internal use only.
     * @param key[IN] the key to insert
     * @param pid[IN] the PageId to insert
     */
    void unchecked_insert(int key, PageId pid);
};

#endif /* BTNODE_H */
